|
In number theory, Euclid's lemma is a lemma that captures a fundamental property of prime numbers, namely: If a prime divides the product of two numbers, it must divide at least one of those numbers. It is also called Euclid's first theorem〔.〕〔.〕 although that name more properly belongs to the side-angle-side condition for showing that triangles are congruent.〔.〕 For example, 133 × 143 = 19019, and since 19019 is divisible by 19, the lemma implies that one or both of 133 or 143 must be as well. In fact, 133 = 19 × 7. This property is the key〔In general, to show that a domain is a unique factorization domain, it suffices to prove Euclid's lemma and ACCP.〕 in the proof of the fundamental theorem of arithmetic. It is used to define prime elements, a generalization of prime numbers to arbitrary commutative rings. The lemma is not true for composite numbers. For example, 4 does not divide 6 and 4 does not divide 10, yet 4 does divide their product, 60. ==Formulations== Let be a prime number, and assume divides the product of two integers and . (In symbols this is written . Its negation, does not divide is written .) Then or (or both). Equivalent statements are: * If and , then . * If and , then . Euclid's lemma can be generalized from prime numbers to any integers: : If , and is relatively prime to , then . This is a generalization because if is prime, either * or * is relatively prime to . In this second possibility, so . 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Euclid's lemma」の詳細全文を読む スポンサード リンク
|